<?php
/**
 * User: LRZ
 * Date: 2020/2/21
 * Time: 10:50
 */

/**
 *  453.最小移动次数使数组元素相等
 *
 *  标签：数学
 *
 *  给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
 *
 *  示例:
 *      输入:[1,2,3]
 *      输出:3
 *      解释：只需要3次移动（注意每次移动会增加两个元素的值）：[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$nums = [1, 2, 3];
$res  = minMoves($nums);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function minMoves($nums)
{
    sort($nums);
    $size = count($nums);
    $res  = 0;
    for ($i = 1; $i < $size; $i++) {
        $diff     = ($res + $nums[$i]) - $nums[$i - 1];
        $nums[$i] += $res;
        $res      += $diff;
    }
    return $res;
}